package leetcode;

import leetcode.util.ListNode;

import java.util.ArrayList;

/**
 * Created by tiang on 2018/11/26.
 * 修改链表结构
 */
public class ReorderList {
    /**
     * 将链表 1-2-3-4-5变成1-5-2-4-3
     * 时间复杂度n2，空间复杂度1，
     * 每次遍历寻找最后一个元素
     * @param head 链表头
     */
    public void reorderList(ListNode head) {
        ListNode pre = head;
        while(pre != null && pre.next!=null) {
            ListNode tail = pre;
            ListNode before = null;
            while (tail.next != null) {
                before = tail;
                tail = tail.next;
            }
            before.next = null;
            tail.next = pre.next;
            pre.next = tail;

            pre = tail.next;
        }
    }

    /**
     * 将链表 1-2-3-4-5变成1-5-2-4-3
     * 时间复杂度和空间复杂度均为n
     * 先采用一个Arraylist记录后半部分的节点，然后将后半部分的节点倒序插入到原链表中
     * @param head 链表头
     */
    public void reorderListII(ListNode head){
        if(head == null)
            return;
        // 根据快慢节点找到链表的中点
        ListNode slow = head,
                fast = head;
        while(fast!=null){
            fast = fast.next;
            if(fast == null)
                break;
            else
                fast = fast.next;
            slow = slow.next;
        }
        if(slow == null)
            return;
        // 将后半部分的节点存入列表
        ArrayList<ListNode> nodeList = new ArrayList<>();
        while(slow.next!=null){
            ListNode temp = slow.next;
            slow.next = null;
            slow = temp;
            nodeList.add(slow);
        }
        // 将后半部分依次插入到原链表中
        ListNode pointer = head;
        for(int i=nodeList.size()-1;i>=0;i--){
            ListNode temp = nodeList.get(i);
            temp.next = pointer.next;
            pointer.next = temp;
            pointer = pointer.next;
            if(pointer.next == null)
                break;
            else
                pointer = pointer.next;
        }
    }
}
